from typing import List


class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        if len(digits) == 10:
            return n

        digits = [int(digit) for digit in sorted(digits)]
        nums = [int(i) for i in str(n)]

        # m1=不包含0的数字个数；m2=包含0的数字个数
        m1, m2 = len(set(digits) - {0}), len(digits)

        # s=n的位数
        s = len(nums)

        ans = 0

        # 处理0开头的情况
        for i in range(1, s):
            ans += m1 * pow(m2, s - i - 1)

        for i in range(s):
            candidates = list(digits)

            # 开头数字不能为0
            if i == 0 and 0 in digits:
                candidates.remove(0)

            for d in candidates:
                # 个位数以上需要小于最大值的当前位
                if d < nums[i]:
                    ans += pow(m2, s - i - 1)

                # 个位数等于最大值的当前位即可
                if d == nums[i] and i == s - 1:
                    ans += 1

            # 如果当前位不在可选数字中，则无法得到更多结果
            if nums[i] not in candidates:
                break

        return ans


if __name__ == "__main__":
    # 20
    print(Solution().atMostNGivenDigitSet(digits=["1", "3", "5", "7"], n=100))

    # 29523
    print(Solution().atMostNGivenDigitSet(digits=["1", "4", "9"], n=1000000000))

    # 测试用例15/84 : 2
    print(Solution().atMostNGivenDigitSet(digits=["1", "4", "9"], n=4))

    # 测试用例37/84 : 2
    print(Solution().atMostNGivenDigitSet(digits=["5", "6"], n=19))
